//
// Created by liushihao on 19-4-26.
//
#include "iostream"
#define Maxsize 100
using namespace std;
typedef char ElemType;
 
typedef struct node
{
    ElemType data;
    struct node *lchild;
    struct node *rchild;
}BTNode;
 
 
 
void CreateBTree(BTNode * &b, char *str) //创造二叉树
{
    BTNode *St[Maxsize], *p;
    int top=-1,k,j=0;
    char ch;
    b=NULL;
    ch=str[j];
    while(ch!='\0')
    {
        switch (ch)
        {
            case '(':top++;St[top]=p;k=1;break;
            case ')':top--;              break;
            case ',':k=2;                break;
            default:
                p=(BTNode*)malloc(sizeof(BTNode));
                p->data=ch;
                p->lchild=p->rchild=NULL;
                if(b==NULL)
                    b=p;
                else
                {
                    switch(k)
                    {
                        case 1:St[top]->lchild=p;break;
                        case 2:St[top]->rchild=p;break;
                    }
                }
        }
        j++;
        ch=str[j];
    }
}
 
void DestroyBtree(BTNode *&b)  //销毁二叉树
{
    if(b!=NULL)
    {
        DestroyBtree(b->lchild);
        DestroyBtree(b->rchild);
        free(b);
    }
}
 
BTNode *FindNode(BTNode *b,ElemType x)
{
    BTNode *p;
    if(b==NULL)
    {
        return NULL;
    }
    else if(b->data==x)
    {
        return b;
    }
    else
    {
        p=FindNode(b->lchild, x);
        if(p!=NULL)
        {
            return p;
        }
        else
        {
            return FindNode(b->rchild, x);
        }
    }
}
 
BTNode *LchildNode(BTNode *p)
{
    return p->lchild;
}
 
BTNode *RchildNode(BTNode *p)
{
    return p->rchild;
}
 
int BTHeight(BTNode *b)
{
    int lchildh,rchildh;
    if(b==NULL) return 0;
    else
    {
        lchildh=BTHeight(b->lchild);
        rchildh=BTHeight(b->rchild);
        return (lchildh>rchildh)? (lchildh+1):(rchildh+1);
    }
}
 
void DispBTree(BTNode *b)
{
    if(b!=NULL)
    {
        cout<<b->data;
        if(b->lchild!=NULL || b->rchild!=NULL)
        {
            cout<<"(";
            DispBTree(b->lchild);
            if(b->rchild!= NULL) cout<<",";
            DispBTree(b->rchild);
            cout<<")";
        }
    }
}